package Graph.graphWithNoweight.leetCode;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/15 11:50
 * @Version 1.0
 *
 * 1 表示起始方格。且只有一个起始方格。
 * 2 表示结束方格，且只有一个结束方格。
 * 0 表示我们可以走过的空方格。
 * -1 表示我们无法跨越的障碍。
 *
 * 其实就是计算共有几条 不同的哈密尔路径
 */
public class leetCode980 {
    private int[][] grid;
    private int R,C;
    private boolean[][] visited;
    private int start,end;
    private int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};

    public int uniquePathsIII(int[][] grid){
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        visited = new boolean[R][C];
        int left = R*C;
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(grid[i][j] == 1){
                    // 把二维的图像 一维化
                    start = i*C +j;
                    //表示i,j 这个点可以走了
                    grid[i][j] = 0;
                }else if(grid[i][j] == 2){
                    end = i*C +j;
                    grid[i][j] = 0;
                }else if(grid[i][j] == -1){
                    left--;
                }
            }
        }
        //只需要计算路径的个数就行了，，不用得到具体路径
        return dfs(start,left);
    }

    //从顶点v 出发还要经过left 个不同点
    private int dfs(int v, int left) {
        // 将一维坐标 转 维二维坐标
        int x = v / C,y = v % C;
        visited[x][y] = true;
        left--;
        if(left == 0 && v == end){
            //left == 0 说明途中点都已近走过一遍了。
            visited[x][y] = false;
            return 1;
        }
        int res = 0;
        for(int d=0;d<4;d++){
            int nextx = x +dirs[d][0],nexty = y+dirs[d][1];
            if(inArea(nextx,nexty) && !visited[nextx][nexty] && grid[nextx][nexty] == 1){
                //深度优先遍历，也是从降维 后的map，并不是邻接矩阵
                res += dfs(nextx*C+nexty,left);
            }
        }
        return 0;
    }

    private boolean inArea(int nextx, int nexty) {
        return nextx >=0 && nextx<R && nexty>=0 && nexty<C;
    }
}
